Static timing analysis (STA) has been widely in industry to determine the latest and earliest possible switching times of various signals within a digital circuit. STA may generally be performed at the transistor level or at the gate level, using pre-characterized library elements, or at higher levels of abstraction, for complex hierarchical chips.
STA algorithms operate by first levelizing the logic structure, and breaking any loops in order to create a directed acyclic graph (timing graph). Modern designs can often contain millions of placeable objects, with corresponding timing graphs having millions, if not tens of millions of nodes. For each node, a corresponding arrival time, transition rate (slew), and required arrival time are computed for both rising and falling transitions as well early and late mode analysis. An arrival time (AT) represents the latest or earliest time at which a signal can transition due to the entire upstream fan-in cone. The slew value is the transition rate associated with a corresponding AT, and a required arrival time (RAT) represents the latest or earliest time at which a signal may transition to satisfy all timing constraints in the entire downstream fan-out cone.
AT's are propagated forward in a levelized manner, starting from the design primary input asserted (i.e., user-specified) arrival times, and ending at either primary output ports or intermediate storage elements. For single fan-in cases,AT sink node=AT source node+delay from source to sink.whenever multiple signals merge, each fan-in contributes a potential arrival time computed asAT sink (potential)=AT source+delay,making it possible for the maximum (late mode) or minimum (early mode) of all potential arrival times to be retained at the sink node. Typically an exact delay value for an edge in a timing graph is not known, but instead only a range of possible delay values can be determined between some minimum delay and maximum delay. In this case, maximum delays are used to compute late mode arrival times and minimum delays are used to compute early mode arrival times.
RATs are computed in a backward levelized manner starting from either asserted required arrival times at the design primary output pins, or from tests. Tests are constraints between pairs of early and late ATs, e.g., setup or hold constraints at internal storage devices. For single fan-out cases,RAT source node=RAT sink node−delay.
When multiple fan-outs merge (or when a test is present), each fan-out (or test) contributes a prospective RAT, enabling the minimum (late mode) or maximum (early mode) required arrival time to be retained at the source node. When only a range of possible delay values can be determined, maximum delay are used to compute late mode required arrival times and minimum delays are used to compute early mode required arrival times.
The difference between the arrival time and required arrival time at a node (i.e., RAT−AT in late mode, and AT−RAT in early mode) is referred to as slack. A positive slack implies that the current arrival time at a given node meets all downstream timing constraints, and a negative slack implies that the arrival time fails at least one such downstream timing constraint. A timing point may include multiple such AT, RAT, and slew values, each denoted with a separate tag, in order to represent data associated with different clock domains (i.e., launched by different clock signals), or for the purpose of distinguishing information for a specific subset of an entire fan-in cone or fan-out cone.
Static timing analysis may also deal with statistical values for ATs, RATs, delays, and other quantities, rather than simple scalar values. In one statistical analysis method each delay DX is modeled as DX=DX0+DX1P1+ . . . DXNpN+DXRΔR, where DX0 is a mean value, DX1, . . . DXN are a set of sensitivity values to a corresponding set p1, . . . pN of independent zero-mean unit-variance random variables representing independent effects (e.g., voltage, temperature, device thresholds, etc.) that can cause various amounts of variation in delays in the network, and DXR is the sensitivity of DX to a separate independent random variable ΔR for each delay that is uncorrelated with variations in other delays. Statistical addition or subtraction of a pair of timing values is performed by adding or subtracting corresponding mean and correlated sensitivity values, and computing the RSS (root sum square) of the independent random sensitivities, e.g., A−B=(A0−B0)+(A1−B1)p1+ . . . (AN−BN)pN+sqrt(AR2+BR2)ΔR.
Due to the impacts of process variability, the common path pessimism removal (CPPR) algorithm, which is described in U.S. Pat. No. 5,636,372 to Hathaway, et. al is an integral component of static timing analysis in order to provide credit for physically common portions of launch and capture data paths feeding a downstream test. In general, the CPPR analysis consists of a path tracing component, wherein common circuit elements feeding both early and late mode arrival times at a downstream test are identified, and credit is computed based on a cancellable difference in early vs. late delays or arrival times for said common circuit elements. In modern chip hierarchical design, however, there are increasing cases where external correlations exist between different asserted arrival times (typically for clock signals), which otherwise would not be considered common circuit elements by prior art CPPR methods, and therefore there is a need for a system and method for performing common path pessimism removal which accounts for correlations between asserted arrival times. Although the CPPR analysis process is described herein as tracing individual paths, it will be understood that alternative embodiments exist, including embodiments that identify data and clock sub-graphs that contain multiple paths originating at a common point, and the CPPR credit analysis methods described herein apply equally to these embodiments.
One such example which illustrates the need to account for correlations between asserted arrival times during CPPR analysis is that of hierarchical static timing analysis, which is used in order to divide analysis of a large design in to smaller and more manageable segments. In one style of hierarchical analysis, a design is partitioned into various modules which are analyzed independently (also referred hereinafter as “out of context” analysis), using asserted input arrival times and output required arrival times. A reduced abstract model is subsequently generated which may remove internal latch to latch logic, and full design timing is subsequently performed using reduced abstract models. During out of context timing analysis, it is generally necessary to run the CPPR algorithm in order to remove undue pessimism from timing slacks in cases where launch and capture paths share common logic, and/or statistical adjustment can be applied to independently random delays in the non-common launching and capture paths. One type of statistical adjustment is RSS credit, in which the independent random contributions from the delays common to the launch and capture paths is removed from the RSS computed independent random portion of the test slack. In some cases, e.g., where a design partition contains multiple clock inputs, it is possible that the aforementioned launching and capturing paths trace back to a pair of different asserted arrival times at the macro boundary, in which case the CPPR algorithm needs external information regarding said different asserted arrival times at macro boundary in order to properly compute credit is due for a downstream test.
Prior art approaches to the aforementioned problem either disallow the interaction between different asserted arrival times, which limits the set of designs for which hierarchical techniques can be fully leveraged, or by require margining to account for the inability to accurately compute CPPR credit in such cases.
One such prior art method handles hierarchical STA including certain limited aspects of CPPR implications by focusing on the need to ensure that the actual early/late arrival time difference for a given pair of signals adjusted by the appropriate CPPR credit (e.g., from an analysis of a pair of clock paths feeding a module instance to be analyzed out of context) is less than the difference in the asserted arrival of those same signals applied for out of context block-level timing. However, there are two problems with the prior art methodologies. First, for multiple interacting clock domains, it is impossible to ensure that all such constraints can be met using absolute arrival times and without introducing additional pessimism.
By way of example, assume three macro input clock arrival times A,B,C, for which the proper early/late arrival time difference (including appropriate CPPR adjust) are identical for all three pairs of signals are identical, i.e., AT(A)−AT(B)=k, AT(A)−AT(C)=k, and AT(B)−AT(C)=k.
It is evident that algebraically, it is not possible to select a consistent set of values for AT(A), AT(B), AT(C) that satisfies all the above equalizers. As a result, using prior art techniques, some additional pessimism must be built in, typically by transforming the equalities above to inequalities, which then results in a requirement to close on timing based on a larger effective clock skew than actually necessary.
Furthermore, the prior art is moot regarding dealing with CPPR analyses within a statistical framework wherein along the non-common path a) statistical adjustment of random delay, and b) cancellation of globally correlated sources of variability become important aspects.
In another illustrative example, designs employing a combination of clock grids and clock trees often contain arrival time assertions at the root of each local clock tree (which are in turn generally fed from a common clock grid), wherein an early/late arrival time difference is introduced in order to account for a worst-case clock grid skew. In such a scenario it is possible that a launch and capture path feeding a downstream test originate from two different local clock trees, however, due to underlying correlations (e.g., physical proximity) it may be considered overly pessimistic to apply a worst-case clock grid skew, and therefore there is a need for a system and method capable of providing CPPR credit due to correlations between different asserted clock arrival times originating from different points in the clock grid.
In a closely related example, an additional early/late arrival time difference may be applied to selected transitions (i.e., rise or fall) at asserted arrival time points in order to account for half-cycle penalties. For example, in order to add timing margin for half-cycle paths, one technique is to apply an additional adjust to the (early or late, or both) trailing clock transition(s) of asserted clock arrival times. In so doing, Lead to Trail, Trail to Lead, and Trail to Trail paths are subject to additional timing margin. Since the intention is to penalize only half-cycle paths, it is subsequently necessary to give credit back for launch and capture path-pairs which both originate back to a Trailing transition asserted clock arrival time. In the case where said asserted Trailing transition clock arrival times correspond to different nodes within the timing graph for the early and late mode paths, there is a need for a system and method capable of providing CPPR credit due to correlations between different asserted arrival times.
Therefore, considering the above cases, there is a need for a system and a method capable of providing the necessary computations of the CPPR credit due to correlations between asserted arrival times, which does not introduce excess pessimism, and further which is amenable to performing statistical CPPR analysis.